#define LH 1
#define EH 0
#define RH -1

typedef struct BiTNode					//定义平衡二叉树的结点
{
	int data;
	int bf;								//平衡因子
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void R_Rotate(BiTree *p)				//右旋
{
	BiTree L;						//L用做中间指针
	L = (*p)->lchild;				//L指向根结点的左子树
	(*p)->lchild = L->rchild;		//拆下根结点的左子树的右子树，作为根结点的左子树
	L->rchild = (*p);				//根结点作为新的根结点的右子树
	*p = L;							//*p指向中间的结点，L的值赋给*p
	
}

void LeftBalance(BiTree *T)	//新插入的接待在左孩子内部
{  
	BiTree L, Lr;
	L = (*T)->lchild;		//L指向传入的树的左孩子
	
	switch(L->bf)
	{
		case LH:						//新插入的结点在左孩子的左子树上，右旋处理
			(*T)->bf = L->bf = EH;		//下一状态，树达到平衡
			R_Rotate(T);				//右旋处理
			break;
		case RH:						//新插入的结点在左孩子的右子树上，双旋处理
			Lr = L->rchild;				//lr指向树的左孩子的右孩子
			
			switch(Lr->bf)				//更新双旋处理之后会影响到的各个结点的BF值
			{
				case LH:						//插入结点后 左孩子的右子树 左边高
					(*T)->bf = RH;				//树的平衡因子设置为右边高，新插入的接待在左孩子的右子树上
					L->bf = EH;					//树的左孩子的平衡因子设置为等高
					break
					
				case EH:						//插入结点后 左孩子的右子树 等高
					(*T)->bf = L->bf = EH;		//树、树的左孩子的平衡因子设置为等高
					break;						
					
				case RH:						//插入结点后 左孩子的右子树 右边高
					(*T)->bf = EH;				//树的平衡因子设置为等高
					L->bf = LH;					//树的左孩子的平衡因子设置为左边高
					break;
			}
			
			Lr->bf = EH;					//更新左孩子的右孩子的BF值，该结点为新的根结点
			
			L_Rotate(&(*T)->lchild);		//左旋
			R_Rotate(T);					//右旋
	}
}

int InsertAVL(BiTree *T, int e, int *taller)		//taller标志树增加结点了没有，增加结点不平衡
{
	if( !*T )				//如果树指针为空，插入结点
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = e;
		(*T)->lchild = (*T)->rchild = NULL;
		(*T)->bf = EH;								//平衡
		*taller = TRUE;								//增加结点的标志位
	}
	else							//树非空，递归搜索到相应位置	
	{
		if(e == (*T)->data)			//树中已经有元素e
		{
			*taller = FALSE;
			return FALSE;
		}
		if(e < (*T)->data)			//小于，向左走
		{
			if(!InsertAVL(&(*T)->lchild, e, taller))	//向左走
			{
				return FALSE;							//如果下一层返回FALSE，本层也返回FALSE
			}
			
			if(*taller)						//如果增加结点了，说明根结点的左子树增加了结点
			{
				switch((*T)->bf)
				{
					case LH:				//原来根结点的左子树高
						LeftBalance(T);		//左边插入，左平衡处理
						*taller = FALSE;	//本层没有增加结点
						break;
					case EH:				//原来根结点等高
						(*T)->bf = LH;		//左边插入，左边高
						*taller = TRUE;		//本层增加结点了
						break;
					case RH:				//原来根结点的右子树高
						(*T)->bf = EH;		//左边插入，两边等高
						*taller = FALSE;	//本层没有增加结点
						break;
				}
			}
		}
		else				//大于，向右走
		{
			if(!InsertAVL(&(*T)->rchild, e, taller))		//向右走
			{
				return FALSE;			//如果下一层返回FALSE，本层也返回FALSE
			}
			
			if(*taller)					//如果增加结点了，说明根结点的右子树增加了结点
			{
				switch((*T)->bf)
				{
					case LH:				//原来根结点的左子树高
						(*T)->bf = EH;		//右边插入，两边等高
						*taller = FALSE;	//本层没有增加结点
						break;
					case EH:				//原来根结点等高
						(*T)->bf = RH;		//右边插入，右边高了
						*taller = TRUE;		//本层增加结点了
						break;
					case RH:				//原来根结点的右子树高
						RightBalance(T);	//右边插入，右平衡操作
						*taller = FALSE;	//本层没有增加结点
						break;
				}
			}
		}
	}
}